package com.lh.leetcodetop100;

import sun.util.resources.cldr.ee.CalendarData_ee_GH;

/**
 * @author: linghao
 * @since: 2022/10/25
 */
public class 两数相加_2 {

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     * 我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为 n1,n2
     * 进位值为 carry，则它们的和为 n1+n2+carry；
     * 其中，答案链表处相应位置的数字为 (n1+n2+carry)mod10，
     * 而新的进位值为 (n1+n2+carry)/10
     * 如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 0 。
     *
     * 此外，如果链表遍历结束后，有 carry>0，还需要在答案链表的后面附加一个节点，节点的值为 carry。
     *
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null,tail = null;
        int carry = 0;  //存放进位值
        while(l1 != null || l2 != null){
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if(head == null){
                head = tail = new ListNode(sum % 10);
            }else{
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null){
                l1 = l1.next;
            }
            if (l2 != null){
                l2 = l2.next;
            }
            if(carry>0){
                tail.next = new ListNode(carry);
            }
        }
        return head;
    }


    class ListNode {
          int val;
          ListNode next;
          ListNode() {}
          ListNode(int val) { this.val = val; }
          ListNode(int val, ListNode next) { this.val = val; this.next = next; }
      }
}
